package com.algorithm.kruskal;

import java.util.ArrayList;
import java.util.Collections;

public class Kruskal {
    //存放边
    private int edgeNum;
    //存放顶点
    private char[] vertexs;
    //邻接矩阵
    private int[][] matrix;


    public static void main(String[] args) {
        char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        //克鲁斯卡尔算法的邻接矩阵
        int matrix[][] = {
                // 说明： 0 是自己，1000 是不能连通
                /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
                /*A*/ {0, 12, 1000, 1000, 1000, 16, 14},
                /*B*/ {12, 0, 10, 1000, 1000, 7, 1000},
                /*C*/ {1000, 10, 0, 3, 5, 6, 1000},
                /*D*/ {1000, 1000, 3, 0, 4, 1000, 1000},
                /*E*/ {1000, 1000, 5, 4, 0, 2, 8},
                /*F*/ {16, 7, 6, 1000, 2, 0, 9},
                /*G*/ {14, 1000, 1000, 1000, 8, 9, 0}};

        //创建KruskalCase 对象实例
        Kruskal kruskal = new Kruskal(vertexs, matrix);
        //输出构建的
        kruskal.print();
        ArrayList<EDate> edges = kruskal.getEdges();
        System.out.println("边的集合为：");
        edges.forEach(System.out::println);
        kruskal.kruskal();
    }


    public Kruskal(char[] vertexs, int[][] matrix) {
        int length = vertexs.length;
        this.vertexs = new char[length];
        //数组为引用变量 this.vertexs = vertexs 对外部数组的改动会影响内部数组
        for (int i = 0; i < length; i++) {
            this.vertexs[i] = vertexs[i];

        }

        this.matrix = new int[length][length];
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                this.matrix[i][j] = matrix[i][j];
                if (this.matrix[i][j] != 1000) {
                    edgeNum++;
                }
            }
        }
        //在一个无向连通图中，邻接矩阵是对称矩阵
        //ab与ba一条边实际上算了两次，在处理的过程中对邻接矩阵的上三角进行遍历
        edgeNum /= 2;
    }

    public void print() {
        System.out.println("邻接矩阵为：");
        for (int[] a : matrix) {
            for (int b : a) {
                System.out.format("%-6d", b);
            }
            System.out.println();
        }
    }

    /**
     * @param ch 传入顶点的值(如A
     * @return 返回顶点的下标，找不到返回-1
     */
    private int getPosition(char ch) {
        for (int i = 0; i < vertexs.length; i++) {
            if (vertexs[i] == ch)
                return i;
        }
        return -1;
    }

    /**
     * 获取图中的边，获取到EDate数组中，最后遍历数组，将边按照权值进行从小到大排序
     */
    private ArrayList<EDate> getEdges() {
        ArrayList<EDate> arrayList = new ArrayList<>(edgeNum);
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = i + 1; j < vertexs.length; j++) {
                if (matrix[i][j] != 1000)
                    arrayList.add(new EDate(vertexs[i], vertexs[j], matrix[i][j]));
            }
        }
        Collections.sort(arrayList);
        return arrayList;
    }

    /**
     * 获取下标为i的顶点的根节点
     * @param ends 用于存放对应下标结点的根结点
     */
    private int getEnd(int[] ends,int i){
        while(ends[i] != i){
            i = ends[i];
        }
       return i;
    }

    public void kruskal(){
        //保存最小生成树中选中的边
        ArrayList<EDate> res = new ArrayList<>();
        int[] ends = new int[vertexs.length];
        //初始化
        for(int i=0 ; i <vertexs.length; i++){
            ends[i] = i;
        }
        ArrayList<EDate> edges = getEdges();
        //一次获取从小到大排好序的边，查看边的两个顶点的根节点是否相同
        //相同，则放弃该边；不相同，则将其中一端的跟结点作为孩子结点指向另一端的根节点
        for(int i = 0 ;i <edges.size();i++){
            EDate date = edges.get(i);
            //获取边的两个顶点坐标
            int p1 = getPosition(date.start);
            int p2 = getPosition(date.end);
            //比较顶点坐标的根节点
            int m = getEnd(ends, p1);
            int n = getEnd(ends,p2);
            if(m!=n) {
                ends[m] = n;
                res.add(date);
            }
        }
        System.out.println("最小生成树为：");
        res.forEach(System.out::println);
    }


    /**
     * 每个实体，表示图中的一条边
     */
    class EDate implements Comparable<EDate> {
        //表示边的一端和另一端
        char start;
        char end;
        //边的权值
        int weight;

        public EDate(char start, char end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "<" + start +
                    "," + end +
                    "> : " + weight;
        }

        @Override
        public int compareTo(EDate o) {
            // this - o :表示从小到大排序
            return this.weight - o.weight;
        }
    }
}

